1. Field of the Invention
The present invention relates to traffic management in a communications network and, in particular, to filtering of traffic in said network. Specifically, it describes a method for assignment of priority numbers to rules. Priority numbers are essential both in organizing rule searches and in detecting administrative errors.
2. Prior Art
The use of filter systems to manage the flow of traffic in a communications network is well known in the prior art. The filter systems include filter rules that are used to test information in a packet.
In some prior art, ways of testing the filter rules are listed sequentially and information from the packet is presented to the first rule in the list. If the packet information passes the requirements of the rule, the action of the rule is applied to the packet. Otherwise, the packet information is then tested against the next rule, and so on. The sequential method of testing rules is straightforward and simple, but slow.
Another prior art method uses decision trees or parallel calculations to test information in the packet against the rules. For example, U.S. Pat. No. 5,546,390 describes a tree structure in which two or more bits from the header of a packet are tested at each node of the tree. Prior art described in that patent discloses techniques consisting of testing individual bits or contiguous blocks of bits (for example, 32 contiguous bits constituting a destination address).
U.S. Pat. No. 5,574,910 also teaches filtering by use of a binary tree search method in which tree nodes use masks and ranges to make decisions.
U.S. Pat. No. 5,761,424 teaches in general terms the use of programmable criteria to accomplish high-speed filtering through bit tests and compares.
Still other filtering techniques are disclosed in U.S. Pat. Nos. 5,530,703; 5,761,424; 5,848,233 and 5,822,527.
It would not be uncommon to find that information, termed the xe2x80x9ckeyxe2x80x9d, in the packet could fit several rules within a database of rules. This condition is termed xe2x80x9cRules Intersectionxe2x80x9d (described hereinafter). Whenever this condition occurs, the system would break down unless a mechanism and method are provided to address this condition. To the best of our knowledge, the prior art does not include the systematic resolution of this problem as disclosed herein. That is, there is a need to provide a mechanism and method that addresses the condition of a packet matching multiple rules. It is this problem the present invention addresses. In addition, the present invention addresses two types of administrative errors, termed xe2x80x9ccyclic dominationxe2x80x9d and xe2x80x9cinclusion of one rule in another,xe2x80x9d resulting in some rules not being referenced. Suffice it to say at this point that both types of errors can cause failure in a filtering system unless they are detected and appropriate corrective actions are taken. The prior art neither addresses nor recognizes these errors in the manner of the present invention, so far as we know.
The present invention addresses the problems by assigning priority numbers to rules. The priority numbers are assigned in an efficient and clear manner so that any two rules that intersect (some keys fit both rules) have necessarily different priority numbers. Rules with the same priority numbers do not intersect.
In assigning priority numbers and in executing related algorithms and methods, the present invention will do the following upon presentation of new rules:
explicitly query the network administrator to enter a domination declaration for every preexisting rule which intersects a new rule;
build the intersection table and the priority number assignments as rules are entered (rules are entered in any order);
alert the network administrator if inconsistencies of two types occur; namely cyclic domination declaration and inclusion declaration;
The present invention prompts the administrator to declare domination relationships only between pairs of rules which intersect. Again, two rules intersect if some key fits both rules.
In a preferred embodiment of the present invention, information is communicated to the administrator by means of computer generated graphics or text or both. The graphical presentation is in the form of a directed non-cycle graph. Specifically, a vertex in the rule set graph (discussed in detail below) corresponds to a rule. Edges connecting rules are drawn precisely if two rules intersect (one key fits both rules). Such an edge is endowed with a pointer designating domination of one rule by another when the administrator declares that domination. The pointer is directed from the lower priority rule to the higher priority rule. Finally, when a new rule has been added and all dominations declared, the present invention tests the rules for consistency. Then the present invention either informs the user of errors and awaits corrections, or notifies the user that the rules are consistent and computes and displays new priority numbers for the rules.
Filter rules are generally expressed in terms of inequalities to be satisfied by the components of a key. An important example concerns IP headers in which the following information is used to make filter decisions:
Source Address (SA) 32 bits often organized into four bytes of eight bits each with a dot (.) designating separation, or equivalently four integers with values in the interval [0, 255] presented with a dot (.) designating separation such as 17.3.1.18, or equivalently one integer with value in the interval [0, 4,294,967,295] such as 285,409,554;
Destination Address (DA) 32 bits often organized into four bytes of eight bits each with a dot (.) designating separation, or equivalently four integers with values in the interval [0, 255] presented with a dot (.) designating separation such as 17.3.1.18, or equivalently one integer with value in the interval [0, 4,294,967,295] such as 285,409,554;
Source Port (SP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];
Destination Port (DP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];
Protocol (P) 8 bits, or equivalently an integer with value in the interval [0, 255].
The above five components are called the five dimensions used in IP filtering or, collectively, the five-tuple.
Every IP filter rule which uses the above data types can be stated as a combination of ten integers, namely, the ten integers being the upper integer and lower integer limits of a rule in the five dimensions.
Thus the above rule specifications can pertain to the important but special case of IP (Internet Protocol) headers. The present invention not only applies to that case but also every other system of filtering on a protocol with fixed format headers. Indeed, the present invention in describing the organizing of filter rules applies to any filtering system, including those filtering on packet data and on variable length keys. The two basic concepts are intersection (two rules intersect if one key fits both) and inclusion (one rule is included in a second if every key that fits the first also fits the second).
Continuing with the example of filtering in IP, any rule can be written as a 10-tuple of integers, the aforementioned upper and lower limits of values of components of keys which fit the rule, in the following form:
(sa, SA, da, DA, sp, SP, dp, DP, p, P)
Here, sa is the lower limit of Source Address, SA is the upper limit of Source Address, da is the lower limit of Destination Address, and so on.
Two rules R1, R2 are defined to intersect if one key fits both. In terms of IP headers, intersection is equivalent to the following 10 statements being all true:
sa1 less than =SA2 da1 less than =DA2 sp1 less than =SP2 dp1 less than =DP2 p1 less than =P2 (intersection) sa2 less than =SA1 da2 less than =DA1 sp1 less than =SP1 dp2 less than =DP1 p2 less than =P1 
The present invention examines all distinct pairs from a set of N rules and finds those pairs which intersect. In a data base, all intersections are entered as a pair of rule labels {i,j } where i and j are in {0, 1, 2, . . . , N-1}, rule i intersects rule j, and i less than j.
Furthermore, the present invention queries the system administrator as a new rule is To added to a rule set about intersections in which the new rule is a member. The query includes asking which of the two intersecting rules (the new rule and a preexisting rule) dominates in the event that one key is tested and fits both rules. The response of the administrator is called declaring domination.
Furthermore, the present invention includes the Priority Number Algorithm as explicitly described below. The value of a priority number is a natural number 1, 2, 3, . . . The subset of rules with highest priority are those not dominated by any other rule, and they all have priority number 1. If one rule or more rules with priority number 1 dominate one rule or more other rules, then those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 2. If one rule or more rules with priority number less than =2 dominate one rule or more other rules, then those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 3. This relationship and priority number allocation is extended by an algorithm in the present invention to all rules.
Furthermore, after all domination relationships between a new rule and all preexisting rules it intersects are explicitly stated as above, the present invention calculates a priority number for each new rule as well as a priority number for all the rules already in the rule set. The present invention uses the Priority Number Algorithm (described in detail below) to accomplish this.
Furthermore, upon allocating priority numbers the present invention then enables a filter rule mechanism to determine which of two or more rules which fit a key to apply. Namely, of all rules which do apply, the one to select is the one rule with highest priority (lowest priority number). The present invention contains a proof that no two rules which intersect can possibly have the same priority number as generated by the Priority Number Algorithm. Hence the problem of which rule to apply is mathematically guaranteed to have a unique and easily decidable answer.
Two administrative errors can occur in filter rule specification; to wit:
rules that can never be logically referenced can be described and entered, wasting resources and falsely suggesting that a certain action will be taken for certain keys; and
circular domination patterns which can make deciding which rule to apply impossible.
The first error type is: if every key which fits rule i also fits rule j (a relationship called inclusion of rule i in rule j, to be defined precisely below for IP headers) and if rule j dominates rule i, then rule i will never be referenced. The second error type is: if several rules intersect with the first dominating the second, the second dominating the third, and so on, and the last dominating the first, then the rules are said to have circular domination. If a key fits all the rules in the cycle, then no rule can be selected for application to the key.
Furthermore, the present invention automatically informs the administrator if either of the above errors is made upon the introduction of a new rule.
The foregoing and other features and advantages of the invention will be more fully described in the accompanying drawings.